1. Field
The disclosed embodiments generally relate to data storage systems. More specifically, the disclosed embodiments relate to the design of a data storage system with a multi-level lookup that facilitates reducing the number of disk seeks involved in accessing data items and handling disk failures.
2. Related Art
Organizations are beginning to use cloud-based storage systems to store large volumes of data. These cloud-based storage systems are typically operated by hosting companies that maintain a sizable storage infrastructure, often comprising many thousands of servers that that are sited in geographically distributed data centers. Customers typically buy or lease storage capacity from these hosting companies. In turn, the hosting companies provision storage resources according to the customer's requirements and then enable the customers to access these storage resources.
In large storage infrastructures comprising thousands of active storage devices, individual storage devices, such as disk drives, routinely fail. Hence, it is important to be able to rapidly recover from such failures. While recovering from a storage device failure, a data storage system typically performs a number of operations, including allocating a new storage device to replace the failed storage device, and obtaining copies of the data items on the failed storage device from other locations in the storage infrastructure. (For fault tolerance reasons, data items are typically stored redundantly across multiple locations to enable copies of data items to be recovered after a storage device failure.) Finally, the data storage system migrates the obtained copies of the data items to the new storage device.
However, note that a failed storage device typically contains many thousands or even millions of data items, so this migration process can be very slow. Moreover, the process of updating the data-access structures that are used to locate the data items can also be very time-consuming. Because a large number of data items typically exists on a failed storage device, modifying the data-access structures for these data items to point to the new storage device can require a large number of updates. Moreover, performing these updates can potentially involve writing to a large number of storage devices containing location information for the data items.
Hence, what is needed is a system that facilitates recovering from storage device failures without having to migrate large numbers of individual data items, and without requiring time-consuming updates to associated data-access structures.